package com.otherTest.conceitHashMap;


import java.util.ArrayList;
import java.util.List;

/**
 * 自定义hashMap 实现类
 *
 * @author Conceit
 * @version 1.0, 2017/5/17
 */
public class HashMapImpl<K, V> implements IHashMap<K, V> {

    //定义map默认length常量
    private static int DEFAULT_LENGTH = 16;

    //定义增量因子常量 即map达到多少就进行扩容 已使用的容量/总容量>0.75
    private static double DEFAULT_ADD_SIZE_FACTOR = 0.75;

    //数组已使用长度
    private static int useLength;

    //定义数组骨架
    private Entry<K, V>[] table = null;

    //定义构造方法1
    public HashMapImpl(int DEFAULT_LENGTH, double DEFAULT_ADD_SIZE_FACTOR) {
        //定义参数异常
        if (DEFAULT_LENGTH <= 0) {
            throw new IllegalArgumentException("定义的map默认长度不合法!" + DEFAULT_LENGTH);
        }
        if (DEFAULT_ADD_SIZE_FACTOR <= 0 || Double.isNaN(DEFAULT_ADD_SIZE_FACTOR)) {
            throw new IllegalArgumentException("定义的map增量因子不合法!" + DEFAULT_ADD_SIZE_FACTOR);
        }
        HashMapImpl.DEFAULT_LENGTH = DEFAULT_LENGTH;
        HashMapImpl.DEFAULT_ADD_SIZE_FACTOR = DEFAULT_ADD_SIZE_FACTOR;
        table = new Entry[DEFAULT_LENGTH];
    }

    //定义构造方法2
    public HashMapImpl() {

        this(DEFAULT_LENGTH, DEFAULT_ADD_SIZE_FACTOR);
    }


    //实现主快存方法
    @Override
    public V put(K k, V v) {
        //计算存入下标 是否达到增量标准
        if (useLength > DEFAULT_LENGTH * DEFAULT_ADD_SIZE_FACTOR) {
            //如果达到增量标准,则进行扩容
            up2Length();
        }
        //获取数组中的下标 通过key计算出hashCode,且hashCode需要在当前数组范围之内
        int index = getIndex(k, table.length - 1);
        //获取该index中的entry对象
        Entry<K, V> entry = table[index];
        //
        if (entry == null) {
            this.table[index] = new Entry<>(k, v, null);
            useLength++;
        } else if (entry != null) {
            //如果该index存在entry对象 则进行挤压
            this.table[index] = new Entry(k, v, entry) {
            };
            //todo
            //index 一样 key的 equals 也一样 则会用传入的新entry对象 代替 旧entry对象
        }
        return table[index].getValue();
    }

    //扩容两倍数组长度
    private void up2Length() {
        //扩容思路并不是简单将数组默认长度*2 而是新建一个二倍list 将旧数组放入到二倍的新数组
        //需要再踩散列
        //对已经形成链表的entry对象进行递归
        //初始化新数组长度
        Entry<K, V>[] newTable = new Entry[DEFAULT_LENGTH * 2];

        //重新计算hash
        againHash(newTable);

        //DEFAULT_LENGTH=DEFAULT_LENGTH*2;


    }

    //重新计算hash
    private void againHash(Entry<K, V>[] newTable) {
        List<Entry<K, V>> entrylist = new ArrayList<>();
        for (int i = 0; i < table.length; i++) {
            //当前entry对象为null直接跳过
            if (table[i] == null) {
                continue;
            }
            //已经存在的entry对象 将不为null的entry对象，已经list代入
            foundEntryByNext(table[i], entrylist);
        }

        //
        if (entrylist.size() >= 0) {
            //初始化数据规整 新的二倍数据量数组代替旧数组
            useLength = 0;
            DEFAULT_LENGTH = DEFAULT_LENGTH * 2;
            table = newTable;
            //取消链表结构
            for (Entry<K, V> entry : entrylist) {
                if (entry.next != null) {
                    entry.next = null;
                }
                put(entry.getKey(), entry.getValue());
            }
        }

    }

    //对entry对象进行检查,只有一个的直接放入新list,对于多个对象的 已经形成链表的进行     递归     直到不为null
    private void foundEntryByNext(Entry<K, V> entry, List<Entry<K, V>> entrylist) {
        //只存在一个对象的entry对象
        if (entry.next == null) {
            entrylist.add(entry);
        }
//        if(entry.next!=null&&entry!=null){
//            entrylist.add(entry);
//            foundEntryByNext(entry,entrylist);
//        }
        //将每个下标中的entry对象 放入list  注意是每个entry对象及他的next 例如每个index中的entry对象
        //1,2,3 会将1,2,3存入一遍     2,3存入一遍     3存入一遍
        if (entry.next != null && entry != null) {
            entrylist.add(entry);
            foundEntryByNext(entry.next, entrylist);
        }
    }

    //获取放入的数组下标
    private int getIndex(K k, int length) {
        //二进制运算 每一位都为1，结果才为1，否则结果为0
        int index = hash(k.hashCode()) & length;
        return index >= 0 ? index : -index;
    }

    //手动实现算法 位运算
    private int hash(int hashCode) {
        // 二进制运算  ^异或运算符  无符号右移(>>>)
        hashCode = hashCode ^ (hashCode >>> 20) ^ (hashCode >>> 12);
        hashCode = hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4);
        return hashCode;
        /*
         * System.out.println(5 ^ 3);//结果为6
         * 5转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
         * 3转换为二进制：0000 0000 0000 0000 0000 0000 0000 0011
         * 6转换为二进制：0000 0000 0000 0000 0000 0000 0000 0110
         * 二进制的每一位进行比较,相同则结果为0，不同则结果为1
         * */

        /* jdk hashMap hash算法
        * static final int hash(Object var0) {
            int var1;
            return var0 == null?0:(var1 = var0.hashCode()) ^ var1 >>> 16;
        }
        * */

    }

    //实现主快取方法
    @Override
    public V get(K k) {
        //获取该K对应的下标
        int index = getIndex(k, table.length - 1);
        //通过下标获取entry对象
        Entry<K, V> entry = this.table[index];

        //判断该对象中next是否为null,如果为null则说明为是该index下的第一个entry对象
        //如果不是则说明还有其他对象,需要对该entry对象进行遍历,并对传入的key进行比较,相等则返回entry对象
        //直到entry对象的next返回null
        if (entry == null) {
            throw new NullPointerException("该下标中的对象为null!");
        }
        while (entry.next == null) {
            if (k.equals(entry.getKey())) {
                return entry.getValue();
            }
        }
        return null;
    }

    //内部类 实现IHashMap的内部接口entry
    public class Entry<K, V> implements IHashMap.Entry<K, V> {
        //局部变量Key
        K k;
        //局部变量Value
        V v;
        //被本对象this 所挤压下去所指向的next对象   链表形式存在
        Entry<K, V> next;

        //定义构造方法 泛型构造方法不用带上泛型 ####
        public Entry(K k, V v, Entry<K, V> next) {
            this.k = k;
            this.v = v;
            this.next = next;
        }


        @Override
        public V getValue() {
            return v;
        }

        @Override
        public K getKey() {
            return k;
        }


    }


}
